1. Field of the Invention
The present invention relates to the field of data compression, and in particular to a method and apparatus for compression of binary data prior to transmission or storage.
2. Background Art
Frequently, it is necessary or desirable to transmit data from one location to another using some form of modulation or to store information on storage media using some encoding algorithm. For example, a text document may be encoded and transmitted between two computers using frequency modulation (FM). Another example is the storage of binary data on a tape drive storage device. It is generally desirable to transmit or store data efficiently, but prior transmission methods are not as efficient as is possible. These limitations can be better understood with a review of modulated transmissions.
Modulation is the addition of information to an electronic, optical or other signal carrier. Modulation can be applied to direct current, to alternating current, and to optical signals (e.g., laser light, or radio or magnetic waves).
For most of radio and telecommunication today, the carrier is alternating current in a given range of frequencies, and common modulation methods include:
Amplitude modulation (AM), in which the amplitude of the transmitted signal is varied over time;
Frequency modulation (FM), in which the frequency of the carrier signal is varied in small but meaningful amounts; and
Phase modulation (PM), in which the natural flow of the alternating current waveform is delayed temporarily.
These are sometimes known as continuous wave modulation methods to distinguish them from pulse code modulation, which is used to encode both digital and analog information in a binary way. Radio and television broadcast stations typically use AM or FM, and most two-way radios use FM.
The transmission rate is the number of information units transmitted per time unit. For example, a network connection may transmit at a Gigabit per second. It is possible to increase the effective transmission rate without increasing the transmission rate. For example, one method of increasing effective transmission rates is to compress the data before it is encoded in the modulated transmission. Since fewer bits are being transmitted, the effective transmission rate is increased.
For example, if a 100 megabyte data file is transmitted at 1 megabyte per second, the entire process will take 100 seconds. However, if the data file is first compressed into a 60 megabyte file, the transmission will require only 60 seconds. While this method can increase effective transmission rates, it is limited by the amount the data file can be compressed before being modulated.
Another method of increasing effective transmission rates is to simply increase the transmission rate. For example, if each bit took 2 seconds to transmit and the rate was increased to transmitting each bit in 1 second, the transmission rate would double. However, this method also increases the maximum frequency of the signal. For example, a modulated carrier signal that had a maximum frequency of 10 MHz would now have a maximum frequency of 20 MHz. Thus, this method cannot be used when the maximum frequency is near some threshold value imposed either by physical limitations (e.g., bandwidth) or protocols of the transmission system.
Embodiments of the present invention are directed to a method and apparatus for compression of binary data. In one embodiment of the present invention, a modulated signal is compressed. In one embodiment, compression of the modulated signal is used in addition to compression of the data before modulation to increase the effective transmission rate. In other embodiments, binary data is compressed prior to being encoded onto magnetic tape or other storage media.
In one embodiment, data is transmitted using an FM signal. The FM signal is compressed without increasing the maximum frequency. In one embodiment, transition bits (e.g., a 1 following a 0, or a 0 following a 1) have a bit period (i.e., the time between successive bits) no smaller than the smallest bit period possible without increasing the maximum frequency. However, non-transition bits (e.g., a 0 following a 0, or a 1 following a 1) have a bit period smaller than that of the transitioning bits. For example, in one embodiment, the bit period of non-transition bits is one-half that of the bit period for transition bits. Thus, a sequence of a transition bit followed by two non-transition bits (e.g., 111 or 000) would be transmitted in two bit periods instead of three.
The maximum frequency is determined by the space between the two transitions that occur most closely together (e.g., 0 to 1 to 0, or 1 to 0 to 1). Since there is still guaranteed to be at least one full bit period between any two transitions, the maximum frequency is unaffected. Thus, the maximum frequency is used, in one embodiment, for synchronization purposes.
In one embodiment, a header sequence is transmitted. In one embodiment, the header sequence is known to the receiving system. Thus, the header sequence is used to synchronize the receiving system. In one embodiment, the header sequence contains a series of transition bits (e.g., 1010 or 0101) to assist in synchronization. In another embodiment, every time a transition bit is received, synchronization is performed. In yet another embodiment, the header contains a non-transition bit (e.g., 10100 or 01011). Because the receiving system knows where the non-transition bit occurs, the system is able to determine the bit period of non-transition bits. Thus, the system is capable of receiving different transitions that each have a different bit period for non-transition bits (e.g., one with a bit period equal to one-half the length of the bit period for transition bits, and another with a bit period equal to one-fifth the length of the bit period for transition bits).
In another embodiment, noise in a transmission is masked using bit period information. When a transition bit occurs, no other transition can be valid until at least the transition bit period has passed. Thus, noise occurring before passage of the transition bit period will not result in an error. This noise immunity property increases as the percentage of transition bits in the data increases.